package com.test.gpa.test.suanfa;

import java.util.*;

public class NewStart {

    class Node {
        Node[] nodes = new Node[2];

        void insert(int num) {
            Node node = this;
            for (int i = 30; i >= 0; i--) {
                int bit = num >> i & 1;
                if (node.nodes[bit] == null) {
                    node.nodes[bit] = new Node();
                }
                node = node.nodes[bit];
            }
        }

        int match(int num) {
            Node node = this;
            int count = 0;
            for (int i = 30; i >= 0; i--) {
                int bit = num >> i & 1;
                int contrary = bit == 1 ? 0 : 1;
                int an = node.nodes[contrary] != null ? contrary : bit;
                count += an << i;
                node = node.nodes[an];
            }
            return count;
        }
    }

    public int findMaximumXOR(int[] nums) {
        Node node = new Node();
        int max = Integer.MIN_VALUE;
        for (int num :
                nums) {
            node.insert(num);
            int match = node.match(num);
            max = Math.max(max, num ^ match);
        }
        return max;
    }


    public int searchInsert(int[] nums, int target) {
        if (target > nums[nums.length - 1]) return nums.length;
        int index = 0;
        for (int i = 0, j = nums.length; i <= j; ) {
            index = (i + j) / 2;
            if (target == nums[index]) {
                return index;
            } else if (target > nums[index]) {
                i++;
            } else {
                j--;
            }
        }
        return index;
    }

    public int searchInsert1(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public int peakIndexInMountainArray(int[] arr) {
        int index = -1;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) return i;
        }
        return index;
    }

    public int singleNonDuplicate(int[] nums) {
        int sum = 0;
        nums = Arrays.copyOf(nums, nums.length + 1);
        nums[nums.length - 1] = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) sum--;
            else sum++;
            if (sum == 1) return nums[i];
        }
        return -1;
    }

    class Solution {
        long[] sums;
        int[] ints;

        long sum;

        public Solution(int[] w) {
            sums = new long[w.length];
            ints = w;
            sums[0] = w[0];
            for (int i = 1; i < w.length; i++) {
                sums[i] = sums[i - 1] + w[i];
            }
            sum = sums[sums.length - 1];
        }

        public int pickIndex() {

            int random = (int) (Math.random() * sum) + 1;
            return binary(random);
        }

        public int binary(int random) {
            int left = 0, right = sums.length - 1;
            int ans = right;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (sums[mid] > random) {
                    ans = mid;
                    right = mid - 1;
                } else left = mid;

            }
            return ints[ans];
        }
    }

    public int mySqrt(int x) {
        long left = 0, right = x;
        long ans = x;
        while (left <= right) {
            long mid = (right - left) / 2 + left;
            if (mid * mid <= x) {
                ans = mid;
                left = mid + 1;

            } else right = mid - 1;
        }
        return (int) ans;
    }

    public int minEatingSpeed(int[] piles, int h) {
        int right = Integer.MIN_VALUE;
        int left = 0;
        for (int arr :
                piles) {
            right = Math.max(right, arr);
        }
        int ans = right;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            long time = getTime(mid, piles);
            if (time <= h) {
                ans = mid;
                right = mid;
            } else left = mid + 1;
        }
        return ans;
    }

    public long getTime(int speed, int[] piles) {
        long count = 0;
        for (int i = 0; i < piles.length; i++) {
            int sum = (speed + piles[i] - 1) / speed;
            count += sum;
        }
        return count;
    }

//    public static void main(String[] args) {
//        TreeNode treeNode = new TreeNode(1);
//        TreeNode treeNode1 = new TreeNode(2);
//        TreeNode treeNode2 = new TreeNode(3);
//        TreeNode treeNode3 = new TreeNode(5);
//        TreeNode treeNode6 = new TreeNode(5);
//        TreeNode treeNode7 = new TreeNode(5);
//        TreeNode treeNode8 = new TreeNode(5);
//        treeNode.left = treeNode1;
//        treeNode.right = treeNode3;
//        treeNode1.left = treeNode2;
//        treeNode1.right = treeNode6;
//        treeNode6.left = treeNode7;
//        treeNode6.right = treeNode8;
//        NewStart newStart = new NewStart();
//        newStart.deepestLeavesSum(treeNode);
//    }

    public int deepestLeavesSum(TreeNode root) {

        return bfs(root);
    }

    public int bfs(TreeNode treeNode) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode);
        int count = 0;
        while (!queue.isEmpty()) {
            count = 0;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                count += poll.val;
                if (poll.left != null) {
                    queue.add(poll.left);

                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
        }
        return count;
    }


    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) return intervals;
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        List<int[]> list = new LinkedList<>();
        int high = intervals.length;
        int weigh = intervals[0].length;
        int[] ints = new int[]{intervals[0][0], intervals[0][1]};
        for (int i = 1; i < high; i++) {
            int a = intervals[i][0];
            int b = intervals[i][1];
            if (a <= ints[1]) {
                ints[1] = Math.max(ints[1], b);
            } else if (a > ints[1]) {
                int[] ints1 = Arrays.copyOf(ints, ints.length);
                list.add(ints1);
                ints[0] = a;
                ints[1] = Math.max(ints[1], b);
            }
            if (i == high - 1) {
                list.add(ints);
            }
        }
        int[][] ans = new int[list.size()][weigh];
        int n = 0;
        for (int[] ints1 :
                list) {
            ans[n][0] = ints1[0];
            ans[n][1] = ints1[1];
            n++;
        }
        return ans;
    }

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int arr1len = arr1.length;
        int arr2len = arr2.length;
        int[] sums = new int[1002];
        for (int i = 0; i < arr1len; i++) {
            sums[arr1[i]]++;
        }
        int[] ints = new int[arr1len];
        int k = 0;
        for (int i = 0; i < arr2len; i++) {
            if (sums[arr2[i]] != 0) {
                for (int j = 0; j < sums[arr2[i]]; j++) {
                    ints[k] = arr2[i];
                    k++;
                }
            }
            sums[arr2[i]] = 0;
        }
        for (int i = 0; i < sums.length; i++) {
            if (sums[i] != 0) {
                for (int j = 0; j < sums[i]; j++) {
                    ints[k] = i;
                    k++;
                }
            }
        }
        return ints;
    }


    public int findKthLargest(int[] nums, int k) {
        fastSort(nums, 0, nums.length - 1);

        return nums[nums.length - k];
    }

    void fastSort(int[] nums, int low, int high) {
        if (low >= high) return;
        int left = low;
        int right = high;
        int num = left;
        while (left < right) {
            for (; right > left && nums[right] > nums[num]; right--) {

            }
            for (; left < right && nums[left] <= nums[num]; left++) {

            }
            if (right > left) {
                swap(nums, left, right);
            }

        }
        swap(nums, left, num);
        fastSort(nums, low, left - 1);
        fastSort(nums, right + 1, high);
    }


    void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;

    }


    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        PriorityQueue<ListNode> listNodes = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        while (head != null) {
            listNodes.add(head);
            head = head.next;
        }
        ListNode poll = listNodes.poll();
        poll.next = null;
        while (!listNodes.isEmpty()) {
            ListNode poll1 = listNodes.poll();
            poll1.next = poll;
            poll = poll1;
        }
        return poll;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> listNodes = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for (int i = 0; i < lists.length; i++) {
            ListNode head = lists[i];
            while (head != null) {
                listNodes.add(head);
                head = head.next;
            }
        }
        ListNode poll = listNodes.poll();
        if (poll != null) {
            poll.next = null;
        }
        while (!listNodes.isEmpty()) {
            ListNode poll1 = listNodes.poll();
            poll1.next = poll;
            poll = poll1;
        }
        return poll;
    }

    public List<List<Integer>> subsets(int[] nums) {
        dolls(0, nums, new LinkedList<>());
        List<List<Integer>> lists=new LinkedList<>();
        for (List<Integer> l :
                list) {
            lists.add(l);
        }
        return lists;
    }

    Set<List<Integer>> list =new TreeSet<>() ;

    public void dolls(int num, int[] nums, List<Integer> list1) {

        List<Integer> list2 = new LinkedList<>(list1);
        list.add(list2);
        for (int i = num; i < nums.length; i++) {
            list1.add(nums[i]);
            dolls(i + 1, nums, new LinkedList<>(list1));
        }
    }

    public List<List<Integer>> combine(int n, int k) {

        doll(1, n, k);
        return linkedList;
    }

    List<List<Integer>> linkedList = new LinkedList<>();
    List<Integer> integerList = new LinkedList<>();

    public void doll(int index, int n, int k) {
        if (integerList.size() + (n - index + 1) < k) {
            return;
        }
        if (integerList.size() == k) {
            linkedList.add(new LinkedList<>(integerList));
            return;
        }
        integerList.add(index);
        doll(index + 1, n, k);
        integerList.remove(integerList.size() - 1);
        doll(index + 1, n, k);

    }


    Deque<Integer> list3 = new LinkedList<>();
    List<List<Integer>> list2 = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0, 0);
        return list2;
    }

    void dfs(int[] candidates, int target, int now, int index) {

        if (now == target) {
            list2.add(new LinkedList<>(list3));
        }
        if (now > target) return;
        for (; index < candidates.length; index++) {
            int candidate = candidates[index];
            list3.add(candidate);
            dfs(candidates, target, now + candidate, index);
            list3.removeLast();
        }
    }



    public static void main(String[] args) {
        NewStart start=new NewStart();
        start.combinationSum2(new int[]{10,1,2,7,6,1,5},8);
    }

    List<List<Integer>> listN ;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Deque<Integer> deque = new LinkedList<>();
        listN = new LinkedList<>();
//        Arrays.sort(candidates);
        dfs9(candidates, target, 0, 0,deque);
        return listN;
    }
    void dfs9(int[] candidate, int target, int index, int num, Deque<Integer> deque ) {

        if (target == num) {
            listN.add(new LinkedList<>(deque));
        }

        for (int i=index; i<candidate.length ; i++) {
            deque.add(candidate[index]);
            dfs9(candidate, target, i + 1, num + candidate[index],deque);
        }

    }


}
